package com.company.arithmetic;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.Scanner;

/**
 * Created by v on 17-5-17.
 */
public class LCS {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("请输入字符串1:");
        String str1=input.next();
        System.out.println("请输入字符串2:");
        String str2=input.next();
        System.out.println("最长子串为:");
        long time=System.currentTimeMillis();
        System.out.println(dp(str1,str2));
        System.out.println();
        System.out.println("运算时间"+(System.currentTimeMillis()-time));
    }

    /**
     *
     * @param str1 第一个序列
     * @param str2 第二个序列
     * @return     最长子序列
     */
    private static String dp(String str1,String str2){
        int[][] map=new int[str1.length()+1][str2.length()+1];

        //动态生成map
        for(int i=1;i<map.length;i++){
            for(int j=1;j<map[i].length;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    map[i][j]=map[i-1][j-1]+1;
                }else {
                    map[i][j]=Math.max(map[i][j-1],map[i-1][j]);
                }
            }
        }

        return recall(map,str1,str2);
    }

    /**
     * 回溯生成最长子序列
     * @param map 动态规划生成的序列长度矩阵
     * @param str1 第一个序列
     * @param str2 第二个序列
     * @return    最长子序列
     */
    private static String recall(int[][] map,String str1,String str2){
        StringBuffer LCS=new StringBuffer();

        int i=str1.length();
        int j=str2.length();
        int current=map[i][j];
        while (current!=0){
            if(current==map[i][j-1]){
                j--;
            }else if(current==map[i-1][j]){
                i--;
            }else {
                LCS.append(str1.charAt(i-1));
                i--;
                j--;
                current=map[i][j];
            }
        }

        return LCS.reverse().toString();
    }
}
